/**
 * 计数排序
 */
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

void countingSort(vector<int> &v, int m)
{
    int *count = new int[m + 1];
    memset(count, 0, sizeof(int) * (m + 1));

    int n = v.size();
    for (int i = 0; i < n; ++i) {
        count[v[i]]++;
    }
    int nIndex = 0;
    for (int i = 0; i <= m; ++i) {
        while (count[i] > 0) {
            v[nIndex++] = i;
            count[i]--;
        }
    }
    delete[] count;
}

void printResult(vector<int> &v)
{
    for (const auto &n : v)
    {
        cout << n << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> vTest = {1, 3, 45, 7, 2, 7, 3, 76};
    printResult(vTest);
    countingSort(vTest, 76);
    printResult(vTest);
    return 0;
}